# 在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。
# 例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
#  现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继
# 承词有许多可以形成它的词根，则用最短的词根替换它。
#
#  你需要输出替换之后的句子。
#
#  示例 1：
# 输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
# 输出："the cat was rat by the bat"
#
#  示例 2：
# 输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
# 输出："a a b c"
import collections
from functools import reduce
from typing import List


class Solution:
    def replaceWords4(self, dictionary, sentence):
        """
        前缀树实现:
        通过dict实现前缀树
        key : 当前字母
        value: trie节点(下一层所有的字母组成的Tire节点  True: 当前这条路径组成的单词) 递归结构
        :param dictionary:
        :param sentence:
        :return:
        """
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()  #
        END = True
        """
        reduce：用trie作为初始值，将这个初始值和root的第一个字母，作为字典__getitem__方法的参数，
        将返回结果和root第二个字母继续作为__getitem__的参数 然后字典的__getitem__方法，第一个参数是一个字典对象，第二个参数是key值
        所以上述过程可以看做如下循环：
            d=trie[root[0]]
            d=d[root[1]]
            d=d[root[2]]
            …… 
        trie的工厂函数是用匿名函数返回一个defaultdict，所以每次调用，返回给d的就是一个defaultdict
        到最后一次，就是d[END]=root
        """
        # 遍历所有词根生成词根的trie
        for root in dictionary:
            reduce(dict.__getitem__, root, trie)[END] = root

        def replace(word):
            cur = trie
            for letter in word:
                if letter not in cur or END in cur:
                    break
                cur = cur[letter]
            return cur.get(END, word)

        return " ".join(map(replace, sentence.split()))

    def replaceWords3(self, dictionary: List[str], sentence: str) -> str:
        """
        解法二：Trie(自己实现Trie)
        :param dictionary:
        :param sentence:
        :return:
        """
        class TrieNode:
            def __init__(self):
                self.children = [None] * 26
                self.isEnd = False

        class Trie:

            def __init__(self):
                self.root = TrieNode()
                pass

            def insert(self, word: str) -> None:
                tmp = self.root
                for s in word:
                    index = ord(s) - 97
                    if not tmp.children[index]:
                        tmp.children[index] = TrieNode()
                    tmp = tmp.children[index]
                tmp.isEnd = True

            def minPrefixLen(self, word: str) -> int:  # 找到给定word在trie中可以匹配的最短前缀长度
                res = 0
                wordLen = len(word)
                cur = self.root
                for i, ch in enumerate(word):
                    index = ord(ch) - 97
                    tmpNode = cur.children[index]
                    if tmpNode:
                        res += 1
                        if tmpNode.isEnd:
                            return res
                        else:
                            cur = cur.children[index]
                    else:
                        if i < wordLen:  # 单词还没匹配完就已经不匹配了，说明没有trie中不存在word的前缀
                            return 0
                return res

        words = sentence.split(" ")
        trie = Trie()
        for s in dictionary:
            trie.insert(s)

        for i in range(len(words)):
            prefixLen = trie.minPrefixLen(words[i])
            if prefixLen > 0:
                words[i] = words[i][0:prefixLen]
        return " ".join(words)

    def replaceWords2(self, dictionary: List[str], sentence: str) -> str:
        """
        将所有词根 dictionary 存储到集合 Set 中。遍历所有单词，判断其前缀是否为词根。
            如果是，则使用前缀代替该单词；
            否则不改变该单词
        :param dictionary:
        :param sentence:
        :return:
        """
        dictionarySet = set(dictionary)
        words = sentence.split(" ")

        def replace(word) -> str:
            for i in range(1, len(words)):
                if word[:i] in dictionarySet:
                    word = word[0:i]
            return word

        return " ".join(map(replace, words))

    def replaceWords1(self, dictionary: List[str], sentence: str) -> str:
        """
        暴力匹配法
        先将dictionary按长度进行排序(保证短的dictionary单词在前)
        然后逐个单词判断是否是以某个dictionary[i]开始，
            如果是则替换
        :param dictionary:
        :param sentence:
        :return:
        """
        dictionary.sort(key=lambda x: len(x))
        words = sentence.split(" ")
        for i in range(len(words)):
            for s in dictionary:
                if words[i].startswith(s):
                    words[i] = s
                    break

        return " ".join(words)

    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        return self.replaceWords4(dictionary, sentence)


if __name__ == "__main__":
    dictionary, sentence = ["cat", "cy", "rat"], "the cattle was rattled by the battery"
    Solution().replaceWords4(dictionary, sentence)
